Ý tưởng thuật toán

1. DFS trên đồ thị vô hướng cũng giống như khám phá mê cung với một cuộn chỉ và một thùng sơn đỏ để đánh dấu, tránh bị lạc. Trong đó mỗi đỉnh s trong đồ thị tượng trưng cho một cửa trong mê cung.
2. Ta bắt đầu từ đỉnh s, buộc đầu cuộn chỉ vào s và đánh đấu đỉnh này "đã thăm". Sau đó ta đánh dấu s là đỉnh hiện hành u.
3. Bây giờ, nếu ta đi theo cạnh (u,v) bất kỳ.
4. Nếu cạnh (u,v) dẫn chúng ta đến đỉnh "đã thăm" v, ta quay trở về u.
5. Nếu đỉnh v là đỉnh mới, ta di chuyển đến v và lăn cuộn chỉ theo. Đánh dấu v là "đã thăm". Đặt v thành đỉnh hiện hành và lặp lại các bước.
6. Cuối cùng, ta có thể đi đến một đỉnh mà tại đó tất cả các cạnh kề với nó đều dẫn chúng ta đến các đỉnh "đã thăm". Khi đó, ta sẽ quay lui bằng cách cuộn ngược cuộn chỉ và quay lại cho đến khi trở lại một đỉnh kề với một cạnh còn chưa được khám phá. Lại tiếp tục quy trình khám phá như trên.
7. Khi chúng ta trở về s và không còn cạnh nào kề với nó chưa bị khám phá là lúc DFS dừng.

Mệnh đề

Gọi G là một đồ thị vô hướng, trên đó ta sẽ thực hiện thao tác DFS với đỉnh bắt đầu là s thì:

1. Phép duyệt sẽ thăm tất cả các đỉnh cùng thành phần liên thông với s.
2. Các cạnh có nhãn "đã thăm" sẽ tạo ra một cây tối đại của thành phần liên thông chứa s.

Chứng minh

1. Khẳng định 1, là hiển nhiên vì DFS duyệt qua tất cả các đỉnh kề với đỉnh hiện hành (có thể chứng minh hoàn chỉnh hơn bằng phản chứng).
2. Khẳng định 2, đúng do ta chỉ đánh dấu các cạnh đi đến một đỉnh mới nên không thể tạo ra chu trình. Như vậy DFS tạo ra một cây. Hơn nữa, DFS thăm tất cả các đỉnh thuộc thành phần liên thông nên cây này là cây tối đại.

Độ phức tạp của thuật toán

1. DFS được gọi đúng 1 lần ứng với mỗi đỉnh.
2. Mỗi cạnh được xem xét đúng 2 lần, mỗi lần từ một đỉnh kề với nó.
3. Với ns đỉnh và ms cạnh thuộc thành phần liên thông chứa s, một phép DFS bắt đầu tại s sẽ chạy với thời gian O(ns + ms) nếu:

• Đồ thị được biểu diễn bằng cấu trúc dữ liệu dạng danh sách kề.
• Đặt nhãn cho một đỉnh là "đã thăm" và kiểm tra xem một đỉnh "đã thăm" chưa tốn chi phí O(degree).
• Bằng cách đặt nhãn cho các đỉnh là "đã thăm", ta có thể xem xét một cách hệ thống các cạnh kề với đỉnh hiện hành nên ta sẽ không xem xét một cạnh quá 1 lần.

Xác định đỉnh kề trong DFS

• Kết quả của DFS phụ thuộc vào cách ta chọn đỉnh kế tiếp.

Xác định đỉnh kề trong Depth-first search

• Nếu ta bắt đầu tại A và thử cạnh nối đến F, sau đó đến B, rồi đến E, C, cuối cùng là G ta được:

Bắt đầu từ A và kết thúc tại G

• Nếu cũng bắt đầu từ A nhưng đi theo trình tự, tập các cạnh đã thăm, backedge và các điểm đệ quy sẽ khác trước.

Bắt đầu từ A nhưng đi theo trình tự tập các cạnh đã thăm.

Chạy từng bước thuật toán

Giờ ta sẽ chạy từng bước thuật toán theo ví dụ trên.

Nguyên lý[2]

Khởi đầu từ một đỉnh, đi theo các cung(cạnh) xa nhất có thể. Trở lại đỉnh của cạnh xa nhất, tiếp tục duyệt như trước, cho đến đỉnh cuối cùng.

Thuật toán Depth-first search

Đoạn này đang chờ cập nhật hướng dẫn chi tiết các bước chạy. Bạn có thể viết thêm cho đoạn này được hoàn thiện hơn. Xem phần trợ giúp để biết thêm về cách sửa đổi bài. Nếu trang này đã hoàn thiện, mời bạn gỡ bản mẫu này. Sửa đổi cuối: 171.245.69.128 (thảo luận · đóng góp) vào 36 ngày trước. (làm mới)

• Bước 1:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 1

• Bước 2:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 2

• Bước 3:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 3

• Bước 4:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 4

• Bước 5:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 5

• Bước 6:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 6

• Bước 7:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 7

• Bước 8:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 8

• Bước 9:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 9

• Bước 10:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 10

• Bước 11:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 11

• Bước 12:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 12

• Bước 13:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 13

• Bước 14:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 14

• Bước 15:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 15

• Bước 16:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 16

• Bước 17:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 17

• Bước 18:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 18

• Bước 19:

Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 19